Efficient computation of approximate pure Nash equilibria in congestion games

摘要

Congestion games constitute an important class of games in which computing anexact or even approximate pure Nash equilibrium is in general {\sfPLS}-complete. We present a surprisingly simple polynomial-time algorithm thatcomputes O(1)-approximate Nash equilibria in these games. In particular, forcongestion games with linear latency functions, our algorithm computes$(2+\epsilon)$-approximate pure Nash equilibria in time polynomial in thenumber of players, the number of resources and $1/\epsilon$. It also applies togames with polynomial latency functions with constant maximum degree $d$;there, the approximation guarantee is $d^{O(d)}$. The algorithm essentiallyidentifies a polynomially long sequence of best-response moves that lead to anapproximate equilibrium; the existence of such short sequences is interestingin itself. These are the first positive algorithmic results for approximateequilibria in non-symmetric congestion games. We strengthen them further byproving that, for congestion games that deviate from our mild assumptions,computing $\rho$-approximate equilibria is {\sf PLS}-complete for anypolynomial-time computable $\rho$.